As a conventional path search device, Patent Document 1 discloses a path planning system for a mobile robot, in which a path for a mobile robot to move from a starting point to a destination is obtained. The path planning system includes: grid map generation means that generates a grid map showing the distribution of spaces occupied by an object, which represents positions and postures in terms of probability, by using a geometric map for the object within an environment; Voronoi diagram generation means that generates a Voronoi diagram using distances according to the uncertainty of the positions and postures of the object, based on the generated grip map; and path search means that searches for a path from a given starting point to a destination, assuming that the possibility of collision with the object and a path length are expressed as costs on the generated Voronoi diagram.
In this configuration, the Voronoi diagram is generated using distances according to the uncertainty of the positions and postures of the object, and the path search is performed by calculating the costs on the weighted Voronoi diagram thus generated, thereby generating a safer path than that obtained by the conventional Voronoi diagram.
As described above, as a conventional path planning technology, a technology is known in which a movement space is approximated in a grid pattern to evaluate the cost of each path connecting grid points adjacent to each other, as disclosed in the above-mentioned Patent Document 1. In such a path search system, the searched path is represented as an assembly of segments each connecting grid points adjacent to each other. Accordingly, the cost of each path is evaluated as the sum of segments.    [Patent Document 1]
Japanese Unexamined Patent Application Publication No. 2005-32196